package com.jinan.algorithm.opposingDoublePointers;

import java.util.*;

public class OpposingDoublePointersTest {
    public static void main(String[] args) {

    }

    /**
     * 2824. 统计和小于目标的下标对数目 <a href="https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/">...</a>
     * 给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。请你返回满足下述条件的下标对 (i, j) 的数目：
     * 0 <= i < j < nums.length
     * nums[i] + nums[j] < target
     *
     * @param nums
     * @param target
     * @return
     */
    public int countPairs(List<Integer> nums, int target) {
//        nums.sort(Integer::compareTo);
        Collections.sort(nums);
        int left = 0;
        int right = nums.size() - 1;
        int ans = 0;
        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }

    /**
     * 16. 最接近的三数之和 <a href="https://leetcode.cn/problems/3sum-closest/">...</a>
     * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target 。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
     * 返回这三个数的和。
     * 假定每组输入只存在恰好一个解。
     *
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int sum = nums[i] + nums[i + 1] + nums[i + 2];
            if (sum > target) {
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                break;
            }

            sum = nums[i] + nums[nums.length - 2] + nums[nums.length - 1];
            if (sum < target) {
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                continue;
            }
            // 双指针
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    ans = sum;
                    return ans;
                }
            }
        }
        return ans;
    }

    /**
     * 18. 四数之和 <a href="https://leetcode.cn/problems/4sum/">...</a>
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
     * 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
     * （若两个四元组元素一一对应，则认为两个四元组重复）：
     * 0 <= a, b, c, d < n
     * a、b、c 和 d 互不相同
     * nums[a] + nums[b] + nums[c] + nums[d] == target
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            long x = nums[i];
            // 去重
            if (i > 0 && x == nums[i - 1]) {
                continue;
            }
            if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if (x + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                long y = nums[j];
                // 去重
                if (j > i + 1 && y == nums[j - 1]) {
                    continue;
                }
                if (x + y + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if (x + y + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                    continue;
                }
                // 双指针
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long sum = x + y + nums[left] + nums[right];
                    if (sum == target) {
                        ans.add(Arrays.asList((int) x, (int) y, nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 611. 有效三角形的个数 <a href="https://leetcode.cn/problems/valid-triangle-number/">...</a>
     * 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        for (int k = 2; k < nums.length; k++) {
            int x = nums[k];
            if (x == 0) {
                continue;
            }
            int left = 0;
            int right = k - 1;
            while (left < right) {
                if (nums[left] + nums[right] > x) {
                    ans += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ans;
    }

    /**
     * 11. 盛最多水的容器 <a href="https://leetcode.cn/problems/container-with-most-water/">...</a>
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
     * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，
     * 使得它们与 x 轴共同构成的容器可以容纳最多的水。
     */
    public int maxArea(int[] height) {
        int ans = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            ans = Math.max(ans, area);
            if (height[left] < height[right]) {
                int pre = height[left];
                left++;
                while (left < right && height[left] <= pre) {
                    left++;
                }
            } else {
                int pre = height[right];
                right--;
                while (left < right && height[right] <= pre) {
                    right--;
                }
            }
        }
        return ans;
    }

    /**
     * 42. 接雨水 <a href="https://leetcode.cn/problems/trapping-rain-water/">...</a>
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     */
    // 前后缀分解
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        // 前缀最大值
        int[] pre_max = new int[n];
        // 后缀最大值
        int[] suf_max = new int[n];
        pre_max[0] = height[0];
        suf_max[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            pre_max[i] = Math.max(pre_max[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            suf_max[i] = Math.max(suf_max[i + 1], height[i]);
        }
        for (int i = 0; i < n; i++) {
            ans = ans + Math.min(pre_max[i], suf_max[i]) - height[i];
        }
        return ans;
    }

    // 双指针
    public int trap2(int[] height) {
        int n = height.length;
        int ans = 0;
        int left = 0;
        int right = n - 1;
        int pre_max = 0;
        int suf_max = 0;
        while (left <= right) {
            pre_max = Math.max(pre_max, height[left]);
            suf_max = Math.max(suf_max, height[right]);
            if (pre_max < suf_max) {
                ans = ans + pre_max - height[left];
                left++;
            } else {
                ans = ans + suf_max - height[right];
                right--;
            }
        }
        return ans;
    }


    /**
     * 283. 移动零 <a href="https://leetcode.cn/problems/move-zeroes/">...</a>
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     *
     * @param nums 待处理数组
     */
    public void moveZeroes(int[] nums) {
        int i = 0, j = 0;
        for (; i < nums.length && j < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j++] = 0;
        }
    }

    /**
     * 3403.从盒子中找出字典序最大的字符串 I <a href="https://leetcode.cn/problems/find-the-lexicographically-largest-string-from-the-box-i/description">...</a>
     * 难度：中等
     * tag:双指针，字符串，枚举
     * description:
     * 给你一个字符串 word 和一个整数 numFriends。
     * Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
     * word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
     * 所有分割出的字符串都会被放入一个盒子中。
     * 在所有回合结束后，找出盒子中 字典序最大的 字符串。
     * restriction:
     * 1 <= word.length <= 5 * 103
     * word 仅由小写英文字母组成。
     * 1 <= numFriends <= word.length
     *
     * @param word       待处理字符串
     * @param numFriends 朋友数量
     * @return 字典序最大的字符串
     * @apiNote 思路：如果固定子串的左端点，那么子串越长，字典序越大。枚举子串的左端点，计算最大子串。由于其余 k−1 个子串必须是非空的，取长度为 1，其余子串的长度之和至少为 k−1。
     * 所以我们枚举的子串，长度至多为 n−(k−1)。
     */
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) return word;
        int n = word.length();
        String ans = "";
        for (int i = 0; i < n; i++) {
            String str = word.substring(i, Math.min(i + n - numFriends + 1,n));
            if (ans.compareTo(str) < 0) {
                ans = str;
            }
        }
        return ans;
    }
}
